package link_list

var m = make(map[*Node]*Node)

// https://leetcode.cn/problems/copy-list-with-random-pointer leetcode-138
func copyRandomList(head *Node) *Node {
	var newHead *Node
	var tmp *Node
	var node *Node

	for head != nil {
		if v, exist := m[head]; exist {
			node = v
		} else {
			node = &Node{Val: head.Val}
			m[head] = node
		}

		if head.Random != nil {
			if v, exist := m[head.Random]; exist {
				node.Random = v
			} else {
				node.Random = &Node{Val: head.Random.Val}
				m[head.Random] = node.Random
			}
		}

		if newHead == nil {
			newHead = node
			tmp = newHead
		} else {
			tmp.Next = node
			tmp = tmp.Next
		}
		head = head.Next
	}
	return newHead
}

func copyRandomList1(head *Node) *Node {
	var deep func(head *Node) *Node
	deep = func(head *Node) *Node {
		if head == nil {
			return head
		}

		if v, exist := m[head]; exist {
			return v
		}

		node := &Node{Val: head.Val}
		m[head] = node

		node.Next = deep(head.Next)
		node.Random = deep(head.Random)
		return node
	}

	return deep(head)
}

func copyRandomList2(head *Node) *Node {
	tmp := head
	for head != nil {
		if _, exist := m[head]; !exist {
			m[head] = &Node{Val: head.Val}
		}

		if head.Random != nil {
			if _, exist := m[head.Random]; !exist {
				m[head.Random] = &Node{Val: head.Random.Val}
			}
		}
		head = head.Next
	}

	var r, result *Node
	for tmp != nil {
		if r == nil {
			r = m[tmp]
			result = r
		} else {
			result.Next = m[tmp]
			result = result.Next
		}
		if tmp.Random != nil {
			result.Random = m[tmp.Random]
		}

		tmp = tmp.Next
	}

	return r
}

func copyRandomList3(head *Node) *Node {
	for node := head; node != nil; node = node.Next.Next {
		node.Next = &Node{
			Val:  node.Val,
			Next: node.Next,
		}
	}

	for node := head; node != nil; node = node.Next.Next {
		if node.Random != nil {
			node.Next.Random = node.Random.Next
		}
	}

	var r, result *Node
	for node := head; node != nil; node = node.Next {
		next := node.Next
		node.Next = node.Next.Next
		if r == nil {
			r = next
			result = r
		} else {
			result.Next = next
			result = result.Next
		}
	}
	return r
}
